Introduction to Machine Learning

Unit 03: Standard and Weighted K-Nearest Neighbors

1. Introduction

The KNN algorithm is the first supervised classification model we will study in depth. Its power comes from beautiful simplicity: to classify a new point, look at the k closest labeled training points and take a majority vote. This unit covers the algorithm's place in the taxonomy of ML methods, distance metrics, the critical choice of k, the equal-vote problem, and how weighted KNN fixes it.

Learning Objectives

2. Theory

2.1 ML Algorithm Taxonomy

Parametric vs. Non-Parametric
Lazy vs. Eager
DimensionParametricNon-Parametric
Parameter countFixed, independent of data sizeGrows with data size
AssumptionsStrong (linearity, normality, …)Few / none
ExamplesLinReg, LogReg, Naïve BayesKNN, Decision Trees, Ensembles
ProsFast, require less dataFlexible, capture complex patterns
ConsToo restrictive if assumptions failNeed more data, computationally costly
DimensionLazy LearningEager Learning
Training phaseStores the data only (zero compute)Builds explicit model immediately
Work happens when?Prediction timeTraining time
Speed: trainFastSlow
Speed: predictSlow (O(n) per prediction)Fast
ExampleKNN, case-based reasoningNeural Nets, LinReg, Trees
KNN is both Non-Parametric and Lazy. That combination makes it simple, flexible, and interpretable — but slow at prediction and hungry for clean, scaled features.

2.2 The Standard (Uniform) KNN Algorithm

  1. Choose integer K = number of nearest neighbors.
  2. Compute the distance between the query instance and every training example.
  3. Sort distances (ascending) and keep the K smallest (the nearest K).
  4. Gather the class labels of those K neighbors.
  5. Return the simple majority class among the K neighbors as the prediction.

Classic k = 3 vs. k = 5 diagram

K-nearest neighbors classification diagram A green query point is classified using two neighborhood rings. The k equals 3 ring contains two red triangles and one blue square, producing Class B. The k equals 5 ring contains two red triangles and three blue squares, producing Class A. K-nearest neighbors classification The class is determined by the majority of neighboring points. Feature space Query-based neighborhood comparison k = 5 ring · larger k = 3 ring New query unknown class Legend Class A Blue square Class B Red triangle New test point Neighborhood results k = 3 2 B · 1 A k = 5 2 B · 3 A Predicted class Using k = 3 Class B majority: 2 / 3 Neighbor vote: the most common class among the selected points determines the prediction.

2.3 Distance Metrics

A valid metric d must satisfy four axioms: non-negativity d(x1,x2) ≥ 0; self-proximity d(x,x) = 0; symmetry d(x1,x2) = d(x2,x1); and triangle inequality d(x1,x2) ≤ d(x1,x3) + d(x3,x2).

Euclidean
Manhattan
Minkowski

L2 norm — straight-line distance between two points in ℝⁿ.

\( d_E(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}) = \sqrt{\sum_{k=1}^{n} \left( x_k^{(i)} - x_k^{(j)} \right)^2} \)

Default scikit-learn metric for KNN; intuitive; sensitive to scale (so always standardize first!).

L1 norm / city-block / taxicab distance — sum of axis-aligned displacements.

\( d_M(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}) = \sum_{k=1}^{n} \left| x_k^{(i)} - x_k^{(j)} \right| \)

More robust to outliers than Euclidean distance; useful when features have mixed types after encoding.

Generalizes both. The order p is a new hyperparameter:

\( d_{\text{Mink}}(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}) = \left( \sum_{k=1}^{n} \left| x_k^{(i)} - x_k^{(j)} \right|^p \right)^{\frac{1}{p}} \)

2.4 Choosing the Right k

kModel ComplexityBehaviorRisk
1 (very small)HighestMemorizes every training point; jagged decision boundaryOverfit — sensitive to noise and outliers
3, 5, 7 (odd)High / MediumFlexible, locally adaptive boundariesBalanced (good default starting point)
≈ √n or 10–20% of nModerateSmoother boundariesUnderfit risk starts growing
n (all points)LowestAlways predicts the majority class — a trivial baselineUnderfit — ignores all local structure

Practical rules of thumb

2.5 Why Scaling Is Mandatory for KNN

The Scaling Catastrophe

Consider two points: Age=28 vs. 38, Salary=$100,000 vs. $150,000. Euclidean distance without scaling:

\( \sqrt{(38-28)^2 + (150{,}000-100{,}000)^2} \approx \sqrt{100 + 2{,}500{,}000{,}000} \approx 50{,}000 \)

The salary difference of $50K completely dominates the 10-year age difference. After standardization, each feature is measured in SD units and both contribute fairly to the distance.

2.6 The Equal-Vote Problem and Weighted KNN

When "1-person-1-vote" goes wrong

K = 5 for a new query point. Neighbors of Class A sit at distances {0.1, 5.0}; neighbors of Class B sit at {4.8, 4.9, 5.1}. Standard KNN votes 3 B > 2 A → predicts B. But the single very close neighbor at distance 0.1 screams A!

The fix: distance-weighted voting. Give each neighbor a weight that decays with distance. Sum weights per class; pick the class with the largest sum.

Common weighting functions (weight w as a function of distance d)

  1. Inverse distance: \( w_i = \dfrac{1}{d_i + \varepsilon} \) — simple, interpretable. The ε prevents division-by-zero on exactly-repeated training points.
  2. 1 − D: First normalize all K distances by the (K+1)th distance to get Dᵢ ∈ [0,1], then wᵢ = 1 − Dᵢ.
  3. Gaussian / RBF kernel: \( w_i = \exp(-D_i^2) \) — smooth, fast-decaying.

Convenience: sklearn.neighbors.KNeighborsClassifier has weights='distance' which uses inverse distance.

2.7 Weighted KNN Scoring Example from the Lecture

Scaled features, query point David needs a Yes/No prediction:

NeighborScaled DistanceClassWeight = 1/d
John0.301Yes3.322
Rachael0.316No3.165
Norah0.631Yes1.585
Jefferson0.832No1.202
Ruth1.000No1.000
Why weighted is nice: It makes the exact value of k much less critical, because the natural fade of 1/d already down-weights the far neighbors regardless of whether k = 5 or 50.

2.8 Characteristics Summary of KNN

3. Interactive Examples

Example 1: Classify a Point with k = 3 and k = 5

Given a tiny 2-D training set. Compute for yourself, then reveal.

PointXYClass
P10.30.7A
P20.20.9B
P30.60.6A
P40.50.1A
P50.70.7B
P60.40.9B
Query Q0.20.6?
Step 1: Compute Euclidean distances from Q to all 6 points (click)

d(Q, P₁) = √[(0.3−0.2)² + (0.7−0.6)²] = √(0.02) ≈ 0.141 (A)

d(Q, P₂) = √[(0.0)² + (0.3)²] = 0.300 (B)

d(Q, P₃) = √[(0.4)² + (0.0)²] = 0.400 (A)

d(Q, P₄) = √[(0.3)² + (0.5)²] = √(0.34) ≈ 0.583 (A)

d(Q, P₅) = √[(0.5)² + (0.1)²] = √(0.26) ≈ 0.510 (B)

d(Q, P₆) = √[(0.2)² + (0.3)²] = √(0.13) ≈ 0.361 (B)

Predictions: (a) k = 3 standard KNN   (b) k = 5 standard KNN.

Sorted distances: {0.141 (A), 0.300 (B), 0.361 (B), 0.400 (A), 0.510 (B), 0.583 (A)}

(a) k = 3 neighbors: {A, B, B} → majority B → Predict Class B.

(b) k = 5 neighbors: {A, B, B, A, B} → 3 B, 2 A → Predict Class B.

Example 2: When Scaling Destroys the Distance

Scale-or-Not Scenario

Two features: house_sqft (range 800–4,000) and num_bedrooms (range 1–6).

House X: 1,200 sqft, 2 beds.   House Y: 1,800 sqft, 3 beds.

Without any scaling, d(X,Y) ≈ √(600² + 1²) ≈ 600 — the bedroom difference is invisible.

  1. What is the qualitative effect of applying Z-score standardization before distance?
  2. If we used Manhattan distance instead of Euclidean on the raw values, would that help?

(a) Standardization rescales each feature to SD units. Typical SDs: sqft ≈ 700, bedrooms ≈ 1.2. SD units difference: sqft 600/700 ≈ 0.86 SD, bedrooms 1/1.2 ≈ 0.83 SD. After standardization, both features contribute approximately equally to the distance — exactly what we want.

(b) No. Manhattan on raw data still sums: 600 + 1 = 601. The bedroom difference still vanishes. All distance metrics need scale alignment when feature scales differ.

Example 3: Weighted KNN vs. Standard KNN

Click to see the scenario. Compute predictions for both variants.

Query point Q. K = 5. Distances and classes of nearest 5: { d=0.05 A, d=0.98 B, d=0.99 B, d=1.00 B, d=1.01 A }.

  1. Prediction of standard KNN?
  2. Prediction of weighted KNN using w = 1 / d?
  3. Why is there a difference? Which is more sensible?

(a) Standard KNN counts: 3 B vs. 2 A → Predict B.

(b) Weights: A gets 1/0.05 + 1/1.01 ≈ 20 + 0.99 = 20.99. B gets 1/0.98 + 1/0.99 + 1/1.00 ≈ 1.02 + 1.01 + 1.00 = 3.03. Weighted sum A > B → Predict A.

(c) Difference arises because that one extremely close neighbor at d = 0.05 is a very strong signal for A. Weighted KNN is more sensible here because it respects proximity. Always compare weights='uniform' vs. weights='distance' in cross-validation.

4. Numerical Solutions

Problem 1: Manhattan, Euclidean, Chebyshev

Two 4-dimensional standardized points: p = [0.1, −0.3, 0.5, 0.0] and q = [0.3, 0.1, −0.2, 0.7]. Compute (a) Manhattan, (b) Euclidean, and (c) Chebyshev distance between them.

📘 Step-by-step solution

First, coordinate-wise differences: p − q = [−0.2, −0.4, 0.7, −0.7]. Absolute values: |p − q| = [0.2, 0.4, 0.7, 0.7].

(a) Manhattan (L1): sum of absolute values.

\( d_M = 0.2 + 0.4 + 0.7 + 0.7 = \mathbf{2.0} \)

(b) Euclidean (L2): root of sum of squares.

\( d_E = \sqrt{0.04 + 0.16 + 0.49 + 0.49} = \sqrt{1.18} \approx \mathbf{1.086} \)

(c) Chebyshev (L∞): largest absolute coordinate difference.

\( d_C = \max(0.2, 0.4, 0.7, 0.7) = \mathbf{0.7} \)

Problem 2: KNN with a Tie and Weighted KNN

K = 4 (deliberately even, so ties can happen). Four nearest neighbors of a query: {d=0.2 → class 0, d=0.3 → class 1, d=0.5 → class 0, d=0.6 → class 1}.

  1. Show that standard KNN gives a perfect 2/2 tie and describe two sensible tiebreakers.
  2. Apply weighted KNN with w = 1 / d. Does this break the tie?
📘 Step-by-step solution

(a) Standard KNN counts: 2 votes for class 0, 2 votes for class 1 → tie 50/50. Common tiebreakers: (i) pick the class of the single nearest neighbor (class 0 wins); (ii) use weighted KNN; (iii) prefer the class with higher overall prior in the whole training set; (iv) randomly sample (weak!).

(b) Weights per neighbor: w(0@0.2) = 5; w(1@0.3) ≈ 3.333; w(0@0.5) = 2; w(1@0.6) ≈ 1.667. Sums: Class 0 total = 5 + 2 = 7; Class 1 total ≈ 3.333 + 1.667 = 5.00.

\( \text{Weighted class 0} = 7 > \text{Weighted class 1} = 5 \implies \text{Predict }\mathbf{0} \)

Yes — weighting cleanly resolves the tie in favor of the closer class-0 neighbors.

Problem 3: Sensitivity of k (Bias-Variance by Hand)

You have 8 training points, 2-D. Two are mislabeled noise: one red in a blue cluster, one blue in a red cluster. Answer qualitatively with justifications:

  1. At k = 1, how do the two noisy points affect predictions in their immediate neighborhoods?
  2. At k = 7, how do they affect predictions?
  3. Which k value has higher variance? Higher bias?
📘 Step-by-step solution

(a) k = 1: The two mislabeled points each "own" a little Voronoi cell around themselves. Any query that lands nearer to them than to any correctly-labeled neighbor will be predicted wrong. That means the decision boundary ripples and changes drastically depending on exactly where the single noise points landed — classic high variance.

(b) k = 7 (out of 8): Every prediction is a near-majority vote over almost the whole dataset. The two noisy points contribute 2/7 of a vote to queries anywhere, shifting every prediction slightly but smoothly toward the wrong class. Decision boundary is very smooth but biased.

(c) k = 1 has higher variance (predictions depend on tiny local subsets; unstable across retraining). k = 7 has higher bias (underfitting — systematically ignoring the local structure). This is the bias-variance tradeoff in action.

5. Try It Yourself

Problem 1 — Minkowski Distance Practice

Two points on a 2-D standardized plane: a = (1.0, −0.5), b = (2.0, 1.5).

  1. Compute Minkowski distance at order p = 1, p = 2, and p → ∞ (Chebyshev).
  2. Verify numerically that d₁ ≥ d₂ ≥ d∞ on this example. Which metric most penalizes large individual coordinate errors?

|Δx| = 1, |Δy| = 2.

(a)

\( d_1 = 1 + 2 = 3 \) \( d_2 = \sqrt{1^2 + 2^2} = \sqrt{5} \approx 2.236 \) \( d_\infty = \max(1, 2) = 2 \)

(b) 3 ≥ 2.236 ≥ 2 ✓ holds. Lower-p metrics penalize large per-coordinate errors less than the sum; but wait — the reverse: higher-p → only the largest coordinate matters. So L∞ is actually the softest on small coordinate errors; L1 (Manhattan) accumulates everything. For penalizing a single bad coordinate, L∞ effectively ignores all the others — this is why L2 is the balanced default.

Problem 2 — Preprocessing Checklist for KNN

You are given an adult-income dataset with these features. For each column, say YES / NO / MAYBE for whether the described transformation should happen before KNN, with a one-sentence justification.

  1. age (years, 17–90) → StandardScaler Z-score?
  2. workclass (Private / Self-emp-not-inc / … / Never-worked) → LabelEncoder to integers 0..7?
  3. education_num (1 = Preschool through 16 = Doctorate) → Leave as is because it's already numeric?
  4. native_country (42 countries) → One-hot encoding to 41 dummy columns?
  5. Rows with missing occupation = ? → Drop rows?
  1. YES. Continuous numeric feature; distance-based algorithm needs all features on SD scale.
  2. NO. Never use LabelEncoder on nominal X features — it creates a fake ordering ("Private" < "Self-emp"?). One-hot encode instead.
  3. MAYBE but still scale it. It is ordinal with known equal-ish steps, so leaving 1..16 is acceptable, but it should still be standardized along with the other numeric columns to avoid 16–1 range dominating SD-unit distances from age/income.
  4. YES. Correct nominal encoding. (Bonus: 41 columns is high-dimensional for KNN, so consider pairing with chi-square feature selection later.)
  5. MAYBE. If "?" is rare and not MCAR, impute or assign a dedicated Missing category + indicator rather than dropping the whole row.
Problem 3 — Weighted KNN with 1−D

We have K = 4 neighbors with distances to query: {1.0, 2.0, 3.0, 4.0}. The (K+1) = 5th neighbor's distance is 5.0 (used for normalization).

  1. Compute normalized distances Dᵢ = dᵢ / dK+1 for i = 1..4.
  2. Compute weights wᵢ = 1 − Dᵢ for each neighbor.
  3. If neighbor classes are {C1, C2, C1, C2} respectively, which class wins the weighted vote?

(a) D = [1/5, 2/5, 3/5, 4/5] = [0.2, 0.4, 0.6, 0.8].

(b) w = 1 − D = [0.8, 0.6, 0.4, 0.2]. (Check: closer points have bigger weights ✓.)

(c) Weighted sums: Class 1 = 0.8 (neighbor 1) + 0.4 (neighbor 3) = 1.2. Class 2 = 0.6 (neighbor 2) + 0.2 (neighbor 4) = 0.8.

\( \text{Winner} = \arg\max(1.2, 0.8) = \mathbf{C1} \)

6. Interactive Quiz

Answer all 5 MCQs. Click on an option to get instant feedback.

Your score: 0 / 5

7. Key Takeaways

  1. KNN is lazy + non-parametric. No training computation, no distributional assumptions, works on any shape of decision boundary — at the cost of slow O(n) predictions.
  2. 5-step algorithm: Choose K, compute all distances, sort, keep K nearest, return their majority class. That's the whole algorithm.
  3. Distance metrics. Euclidean (L2) is the intuitive default; Manhattan (L1) is more outlier-robust; Minkowski generalizes both via order p.
  4. K controls the bias-variance tradeoff. Small k → flexible, high variance, overfit risk. Large k → smooth, high bias, underfit risk. Tune via cross-validation; use odd k to avoid 2-class ties.
  5. Scale before KNN, always. Standardization (Z-score) usually beats Min-Max here. Skip scaling → the highest-range feature essentially becomes the only feature.
  6. Weighted KNN fixes the equal-vote problem. Use w = 1/d, or w = 1−D normalized, or Gaussian kernels. sklearn parameter: weights='distance'.
  7. Weighting is a safety net. It reduces the sensitivity to the exact value of k because distant neighbors' contributions naturally fade. Always compare weighted vs. uniform during model selection.

8. Common Pitfalls

  1. Forgetting to standardize features. Probably the #1 bug in beginner KNN code. A salary column in cents vs. age in years will make the distance function useless.
  2. Choosing k using test-set performance. Test set should be used once, at the very end. Pick k via cross-validation on the training set — then evaluate final model once on the held-out test set.
  3. Running brute-force KNN on 10⁶ training rows. Prediction is O(n) per query. For medium/large datasets use sklearn's algorithm='ball_tree' or 'kd_tree' to get sublinear queries.
  4. Using weighted KNN without scaling. 1/d weighting compounds the scaling problem: an unscaled distance of 50,000 vs. 10 makes a mess of inverse distances, producing zero useful weights.
  5. Setting k to n. Trivially predicts the majority class — good as a baseline only. Any real dataset has local structure that k = n simply ignores.
  6. Applying KNN to extremely high-dim data without feature selection. The curse of dimensionality (Unit 6) makes all neighbors equally distant, so KNN degenerates into a coin flip.

9. Resources